<?php
/**
 * @title 347. 前 K 个高频元素 - 二分排序
 * @author start2004
 */

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer[]
     */
    function topKFrequent($nums, $k) {
        /**
         * @since 2020-09-07 哈希计数
         */
        $hashs = [];
        foreach ($nums as $num){
            if(isset($hashs[$num])){
                $hashs[$num] += 1;
            } else {
                $hashs[$num] = 1;
            }
        }
        // return $hashs;

        /**
         * @since 2020-09-07 维持一个list队列
         */
        $i = 0;
        $list = [];
        foreach ($hashs as $num=>$count){
            // echo "num={$num}, count={$count}", PHP_EOL;
            $i++;

            /**
             * @since 2020-09-07 前k个元素直接入队列
             */
            if($i==1){
                $list[] = [$num, $count];
                // var_dump($list);
                // echo str_repeat(PHP_EOL, 3);
                continue;
            } elseif($i<=$k){
            } else {
                /**
                 * @since 2020-09-07 比第k个频率元素出现次数更少
                 */
                if($count <= $list[$k-1][1]){
                    continue;
                } else {}
            }

            /**
             * @since 2020-09-07 从大到小, 升序排列
             */
            $left = 0;
            $right = count($list)-1;
            while($left<=$right){
                $midKey = ($right+$left)>>1;
                $midCount = $list[$midKey][1];

                if($count >= $midCount){
                    $right = $midKey-1;
                } else {
                    $left = $midKey+1;
                }
            }

            /**
             * @since 2020-09-07 在right位置插入元素
             */
            // echo "left={$left}, right={$right}", PHP_EOL;
            array_splice($list, $left, 0, [[$num, $count]]);
            // var_dump($list);

            /**
             * @since 2020-09-07 删除最后一位
             */
            if($i>$k){
                unset($list[$k]);
            } else {}
            // echo str_repeat(PHP_EOL, 3);
        }

        /**
         * @return
         */
        // return $list;
        return array_column($list, 0);
    }
}




/**
 * @url http://127.0.0.1/leetcode/202007/2020.07.30_9.php
 */
$datas = [
    [[1,1,1,2,2,3], 2],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->topKFrequent($data[0], $data[1]);
    var_dump($result);
    echo str_repeat("<br>", 3);
}
$xhprof->end();
